899F - Letters Removing - CodeForces Solution

//https://codeforces.com/contest/899/problem/F
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define PI acos(-1)
#define LSB(i) ((i) & -(i))
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define sc second
#define th third
#define fo fourth
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ldb double
#define INF 1e15
#define MOD 1000000007
#define endl "\n"

#define all(data)       data.begin(),data.end()
#define TYPEMAX(type)   std::numeric_limits<type>::max()
#define TYPEMIN(type)   std::numeric_limits<type>::min()
#define MAXN 200007
#define MAXA 256
ll t[4*MAXN],obrisan[MAXN],pos[MAXN];
set<ll> s[MAXA];
void Build(ll v,ll tl,ll tr)
{
    if(tl==tr) t[v]=1;
    else
    {
        ll mid=(tl+tr)/2;
        Build(2*v,tl,mid);
        Build(2*v+1,mid+1,tr);
        t[v]=t[2*v]+t[2*v+1];
    }
}
void Update(ll v,ll tl,ll tr,ll itr)
{
    if(tl==tr) t[v]=0;
    else
    {
        ll mid=(tl+tr)/2;
        if(itr<=mid) Update(2*v,tl,mid,itr);
        else Update(2*v+1,mid+1,tr,itr);
        t[v]=t[2*v]+t[2*v+1];
     }
}
ll Query(ll v,ll tl,ll tr,ll l,ll r)
{
    if(l>r) return 0;
    else if(tl==l && tr==r) return t[v];
    else
    {
        ll mid=(tl+tr)/2;
        return Query(2*v,tl,mid,l,min(mid,r))+Query(2*v+1,mid+1,tr,max(mid+1,l),r);
    }
}
/*ll Walk(ll x,ll n)
{
    ll l=1,r=n,levi,desni,v=1,rez;
    if(x>=t[1]) return n;
    while(l<=r)
    {
        ll mid=(l+r)/2;
        levi=t[2*v]; desni=t[2*v+1];
        if(levi==x) rez=mid;
        if(levi>=x) {r=mid; v=2*v;}
        else {l=mid+1; x-=levi; v=2*v+1;}
    }
    return rez;
}*/
ll Walk(ll x,ll n)
{
    ll l=1,r=n,rez;
    while(l<=r)
    {
        ll mid=(l+r)/2;
        ll levi=Query(1,1,n,1,mid);
        if(levi==x) rez=mid;
        if(levi>=x) r=mid-1;
        else l=mid+1;
    }
    return rez;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    ll n,m,l,r; char c; cin>>n>>m;
    string ss; cin>>ss;
    for(int i=1;i<=n;i++) s[ss[i-1]].insert(i);
    Build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        cin>>l>>r>>c;
        l=Walk(l,n); r=Walk(r,n);
        auto it1=s[c].lower_bound(l),it2=s[c].upper_bound(r);
        for(auto it=it1;it!=it2;it++)
        {
            obrisan[*it]=1;
            Update(1,1,n,*it);
        }
        s[c].erase(it1,it2);
    }
    for(int i=1;i<=n;i++)
    {
        if(!obrisan[i]) cout<<ss[i-1];
    }
    return 0;
}